package com.company.剑指offer每日刷题.普通版;

import javax.swing.tree.TreeNode;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

/**
 * 剑指 Offer 54. 二叉搜索树的第k大节点
 * 给定一棵二叉搜索树，请找出其中第 k 大的节点的值。
 *
 *
 *
 * 示例 1:
 *
 * 输入: root = [3,1,4,null,2], k = 1
 *    3
 *   / \
 *  1   4
 *   \
 *    2
 * 输出: 4
 * 示例 2:
 *
 * 输入: root = [5,3,6,2,4,null,null,1], k = 3
 *        5
 *       / \
 *      3   6
 *     / \
 *    2   4
 *   /
 *  1
 * 输出: 4
 * 限制：
 *
 * 1 ≤ k ≤ 二叉搜索树元素个数
 * */
public class KthLargest {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) { val = x; }
    }
    /**
     * 方法：中序遍历
     * 思路：在二叉搜索树中，
     *      1.从根节点中序遍历二叉树，可以得到一个升序数列
     *      2.       后序遍历的
     *
     * */
    public int kthLargest(TreeNode root, int k) {
        Stack<TreeNode> stack = new Stack<>();
        ArrayList<Integer> list = new ArrayList<>();
        while(root != null && !stack.isEmpty()){
            if(root != null){
                stack.push(root);
                root = root.left;
            }else{
                TreeNode node = stack.pop();
                list.add(node.val);
                root = node.right;
            }
        }
        return list.get(list.size() - k);
    }

    public static void main(String[] args) {
        int k = 5;
        if((--k)==0){
            System.out.println(k);
        }
    }
}
